package com.atguigu.dp;

//使用动态规划解决最大子数组和问题
public class P53_1 {
    public static void main(String[] args) {
        //期望输出：6
        int[] arr =  {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
    }

    private static int max = Integer.MIN_VALUE ;
    private static int maxSubArray(int[] arr) {

        //dp用于记录以i结尾的最大子数组和
        //dp[0]记录以i=0结尾 ， dp[1]记录以i=1结尾的最大子数组和
        int[] dp = new int[arr.length];

        dp[0] = arr[0];
        /*
        dp[1] = Math.max(arr[0]+arr[1],arr[1]);
        dp[2] = Math.max(dp[1] + arr[2] , arr[2]);
        dp[3] = Math.max(dp[2] + arr[3] , arr[3]);
        */
        for(int i = 1 ; i<arr.length ; i++){
            dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);
            max = Math.max(max , dp[i]);
        }
        return max ;
    }
}
